package 力扣.树.中序遍历;


import sun.reflect.generics.tree.Tree;

public class 删除二叉搜索树中的节点450 {
    private void swapValue(TreeNode a, TreeNode b) {
        int t = a.val;
        a.val = b.val;
        b.val = t;
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        //三种情况
        if (root.val > key){
            root.left = deleteNode(root.left, key);
        }
        if (root.val < key){
            root.right = deleteNode(root.right, key);
        }
        if (root.val == key){
            //四种情况
            if (root.left == null && root.right == null){//叶子节点
                return null;
            }
            if (root.left != null){//寻找左子树的最大值
                TreeNode te = root.left;
                while (te.right != null){
                    te = te.right;
                }
                swapValue(te, root);
                root.left = deleteNode(root.left, key);
            }else if (root.right != null){//寻找右子树的最大值
                TreeNode te = root.right;
                while (te.left != null){
                    te = te.left;
                }
                swapValue(te, root);
                root.right = deleteNode(root.right, key);
            }
        }
        return root;
    }


    public TreeNode deleteNode2(TreeNode root, int key) {
          if (root == null){
              return null;
          }
          if (root.val > key){
               root.left = deleteNode2(root.left, key);
          }
          if (root.val < key){
               root.right = deleteNode2(root.right, key);
          }
          if (root.val == key){
              if (root.left == null && root.right == null){
                  return null;
              }
              if (root.right != null){//寻找右子树的最小值
                  TreeNode te = root.right;
                  while (te.left != null){
                      te = te.left;
                  }
                  swapValue(root, te);
                  root.right = deleteNode2(root.right, key);
                  return root;
              }
              if (root.left != null){//寻找左子树的最小值
                  TreeNode te = root.left;
                  while (te.right != null){
                      te = te.right;
                  }
                  swapValue(root, te);
                  root.left = deleteNode2(root.left, key);
                  return root;
              }
          }
          return root;
    }


}
